package com.zhugang.week13.dp;

/**
 * @program algorithms
 * @description: BagesByBacktrack
 * @author: chanzhugang
 * @create: 2022/09/14 23:15
 */
public class BagesByBacktrack {


    /**
     * 0-1背包问题：可装最大重量？
     * 回溯解决
     *
     * @param i
     * @param cw
     */
    private int maxW = Integer.MIN_VALUE;

    private int[] weight = {2, 2, 4, 6, 3};

    private int n = 5;
    // 背包重量
    private int w = 9;

    private boolean[][] mem = new boolean[5][10];

    public void f(int i, int cw) {
        // 回溯模版
        if (i == n || cw == w) {
            if (cw > maxW) {
                // 更新最大值
                maxW = cw;
            }
            return;
        }
        if (mem[i][cw]) return;
        mem[i][cw] = true;

        // 不装入背包
        f(i + 1, cw);
        if (cw + weight[i] <= w) {
            // 装入背包
            f(i + 1, cw + weight[i]);
        }
    }

    public static void main(String[] args) {
        BagesByBacktrack bagesByBacktrack = new BagesByBacktrack();
        bagesByBacktrack.f(0, 0);
        System.out.println(bagesByBacktrack.maxW);
    }
}